home *** CD-ROM | disk | FTP | other *** search
/ Sprite 1984 - 1993 / Sprite 1984 - 1993.iso / man / lib / c / Hash.man < prev    next >
Encoding:
Text File  |  1988-12-30  |  2.4 KB  |  50 lines
  1. ' $Header: /sprite/src/lib/c/hash/RCS/Hash.man,v 1.1 88/12/30 15:05:14 ouster Exp $ SPRITE (Berkeley)
  2. .so \*(]ltmac.sprite
  3. .HS Hash lib
  4. .BS
  5. .SH NAME
  6. Hash \- overview of routines to manipulate hash tables
  7. .BE
  8.  
  9. .PP
  10. The Hash_ routines provide mechanisms for manipulating hash
  11. tables.  A hash table is a data structure that stores any
  12. number of entries, each of which is a <key, value> pair.
  13. Given the key for a particular entry, the
  14. Hash_ routines can very quickly find the entry (and hence the
  15. associated value).  There can be at most one entry with a given
  16. key in a hash table at a time, but many entries may have the
  17. same value.
  18. .PP
  19. This library provides two unusual features.  First, hash tables
  20. can grow gracefully.  In most hash table implementations
  21. the  number of buckets in the table is fixed;  if the number of
  22. entries in the table becomes substantially larger than the number
  23. of buckets, the performance of the table degrades.  In contrast,
  24. this implementation automatically re-allocates the bucket memory
  25. as the table grows.  As a result, hash tables can become arbitrarily
  26. large without overloading the buckets.  An initial number of buckets
  27. may be provided when tables are initialized, but it will change later
  28. (automatically) if necessary to guarantee efficient operation.
  29. .PP
  30. The second unusual feature of the Hash_ routines is that they allow
  31. keys to be expressed in several forms.  Keys may either be variable-length
  32. NULL-terminated strings, or single-word values, or multi-word records
  33. of any length (in the latter case, all keys in the table must be the
  34. same length).  See Hash_InitTable for deatils on the different key types.
  35. .PP
  36. Hash tables are initialized by calling \fBHash_InitTable\fR.  New entries
  37. are added with \fBHash_CreateEntry\fR, and existing entries may be located
  38. with either \fBHash_CreateEntry\fR or \fBHash_FindEntry\fR.  The values stored
  39. in entries are manipulated with \fBHash_GetValue\fR and Hash_SetValue
  40. (values may be arbitrary one-word values; they are stored in entries
  41. and retrieved from them using the type ``ClientData'').  An entry
  42. can be deleted from the table by calling \fBHash_DeleteEntry\fR;  the entire
  43. table can be released by calling \fBHash_DeleteTable\fR.  \fBHash_EnumFirst\fR
  44. and \fBHash_EnumNext\fR provide a facility for stepping through all the
  45. entries in a table.  Finally, \fBHash_PrintStats\fR can be invoked to print
  46. out some usage information about a hash table.
  47.  
  48. .SH KEYWORDS
  49. hash table, key, value
  50.